简要题解
Part1 预处理子集最大团
定义: 是集合 的最大团大小, 是点 的邻居的集合
对于任意一个 ,取任意 ,考虑 是否在最大团中,可以得到转移:
状压从小到大枚举 ,dp 计算即可
注意到我们只需要对每个子集大小分别求出子集最大团的和
所以数组可以开大小 的char类型,因为后 个值不会再次被用到了
Part2 计算贡献
如果在第 回合结束后剩下一个大小为 的子集,包含这种状态的方案数应该是
也就是,考虑每个点是在哪一回合删除的
由于 的范围只有 所以可以枚举,所以要求的就是
这是个关于 的 次多项式,暴力求 个点值然后拉格朗日插值即可
Part3 卡常
这个……看标程吧,最大点 356ms,还挺快的(初代标程最大点 700+ms,
被我优化了一半常数,我认为有必要区分一下)
标程长这样,欢迎抄题解
#include <cstdio>
#include <algorithm>
#define N 28
#define P 1000000007
int n, m, k, G[N], s[N+1]; char a[1<<(N-1)];
int inv[N+2], pow[N+2][N+1];
int main() {
scanf("%d%d%d", &n, &m, &k);
while (m--) {
int x, y;
scanf("%d%d", &x, &y);
G[x] |= 1 << y;
G[y] |= 1 << x;
}
for (int x = 1, t = 1, d = 0; ; x++) {
if (x & (t<<1)) {t <<= 1; if (++d == n-1) break; }
a[x] = std::max(a[x^t], char(a[x&G[d]]+1));
int c = __builtin_popcount(x); s[c] += a[x];
s[c+1] += std::max(int(a[x]), a[x&G[n-1]]+1);
}
s[1]++;
pow[0][0] = inv[1] = 1;
for (int i = 1; i <= n+1; i++) {
pow[i][0] = 1;
for (int j = 1; j <= n; j++)
pow[i][j] = 1ll * pow[i][j-1] * i % P;
}
for (int i = 2; i <= n+1; i++)
inv[i] = 1ll * (P-P/i) * inv[P%i] % P;
int ans = 0;
for (int g = 1; g <= n; g++) {
for (int i = 1; i <= n+1; i++) {
int y = 0;
for (int j = 1; j <= i; j++)
y = (1ll * pow[j][n-g] * (pow[i-j+1][g] - pow[i-j][g] + P) + y) % P;
for (int j = 0; j <= n+1; j++) if (i != j)
y = 1ll * y * (k-j+P) % P * (i>j?inv[i-j]:P-inv[j-i]) % P;
ans = (1ll * y * s[g] + ans) % P;
}
}
printf("%d\n", ans);
}